import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/23 10:12
 * @description 思路：每次查询都O(n)遍历统计次数将超时，那么可以用Hash表 + 存储相同元素出现的下标，
 * 然后进行两次二分查找，找出第一次大于等于left的元素下标和第一次小于等于right的元素下标，两者相减就是[left, right] 之间出现的相同元素次数
 */
public class Solution {
    public static void main(String[] args) {

    }
}

class RangeFreqQuery {

    Map<Integer, List<Integer>> map;

    public RangeFreqQuery(int[] arr) {
        map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], new ArrayList<>());
            }
            map.get(arr[i]).add(i);
        }
    }

    public int query(int left, int right, int value) {
        if (!map.containsKey(value)) {
            return 0;
        }
        List<Integer> list = map.get(value);
        int n = list.size();
        if (right < list.get(0) || left > list.get(n - 1)) {
            return 0;
        }
        // 第一次二分查找左端点下标
        int l = binarySearch(left, list);
        int r = binarySearch(right, list);
        // 对于右端点，要的是第一次小于等于right的数，如果下标表示的list恰好相等，那么无需改变，如果大于，那么左边就是小于等于right的数，需要减一。
        if (list.get(r) > right) {
            r--;
        }
        return r - l + 1;
    }

    /**
     * 查找第一个大于等于index的下标
     * @param index index
     * @param list list
     * @return index
     */
    public static int binarySearch(int index, List<Integer> list) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (list.get(mid) < index) {
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return l;
    }
}
